#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

int deleteAndEarn(vector<int>& nums) {
    int maxn = 0;
    int n = nums.size();
    for (auto x : nums)
        if (x > maxn) maxn = x;
    vector<int> v(maxn + 1);
    for (int i = 0; i < n; i++)
    {
        v[nums[i]] += nums[i];
    }
    vector<int> f(maxn + 1), g(maxn + 1);
    for (int i = 1; i < maxn + 1; i++)
    {
        f[i] = g[i - 1] + v[i];
        g[i] = max(g[i - 1], f[i - 1]);
    }
    return max(f[maxn], g[maxn]);
}
int minCost(vector<vector<int>>& costs) {
    int n = costs.size();
    vector<vector<int>> dp(n, vector<int>(3));
    dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2];
    for (int i = 1; i < n; i++)
    {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
        dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i][2];
    }
    return min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
}

int movesToMakeZigzag(vector<int>& nums) {
    int ret1 = 0, ret2 = 0, n = nums.size();
    for (int i = 0; i < n; i += 2)
    {
        if (i == 0)
        {
            while (nums[i] >= nums[i + 1])
                nums[i]--, ret1++;
        }
        else if (i == n - 1)
        {
            while (nums[i] >= nums[i - 1])
                nums[i]--, ret1++;
        }
        else
        {
            while (nums[i] >= nums[i - 1] || nums[i] >= nums[i + 1])
                nums[i]--, ret1++;
        }
    }
    for (int i = 1; i < n; i += 2)
    {
        if (i == n - 1)
        {
            while (nums[i] >= nums[i - 1])
                nums[i]--, ret2++;
        }
        else
        {
            while (nums[i] >= nums[i - 1] || nums[i] >= nums[i + 1])
                nums[i]--, ret2++;
        }
    }
    return min(ret1, ret2);
}
int main()
{
    vector<int> v{ 2,1,2 };
    deleteAndEarn(v);
    movesToMakeZigzag(v);
	return 0;
}